package Chapter2;

public class SinglyList<T> {
    public Node<T> head;

    public SinglyList() {
        this.head = new Node<T>();
    }

    public SinglyList(T[] values) {
        this();
        Node<T> rear = this.head;
        for (int i = 0; i < values.length; i++) {
            if (values[i] != null) {
                rear.next = new Node<T>(values[i], null);
                rear = rear.next;
            }
        }
    }

    public SinglyList(SinglyList<T> list) {
        this();
        Node<T> rear = this.head;
        for (Node<T> p = list.head.next; p != null; p = p.next) {
            rear.next = new Node<T>(p.data, null);
            rear = rear.next;
        }
    }

    public boolean isEmpty() {
        return this.head.next == null;
    }

    public T get(int i) {
        Node<T> p = this.head.next;
        for (int j = 0; p != null && j < i; j++)
            p = p.next;
        return (i >= 0 && p != null) ? p.data : null;
    }

    public void set(int i, T x) {
        Node<T> p = this.head.next;
        for (int j = 0; p != null && j < i; j++)
            p = p.next;
        p.data = x;
    }

    public int size() {
        int i = 0;
        for (Node<T> p = this.head.next; p != null; p = p.next)
            i++;
        return i;
    }

    public String toString() {
        String str = this.getClass().getName() + "(";
        for (Node<T> p = this.head.next; p != null; p = p.next)
            str += p.data.toString() + (p.next != null ? "," : "");
        return str + ")";
    }

    public Node<T> insert(int i, T x) {
        if (x == null)
            return null;
        Node<T> front = this.head;
        for (int j = 0; front.next != null && j < i; j++)
            front = front.next;
        front.next = new Node<T>(x, front.next);
        return front.next;
    }

    public Node<T> insert(T x) {
        return insert(Integer.MAX_VALUE, x);
    }

    public T remove1(int i) {
        Node<T> front = this.head;
        for (int j = 0; front.next != null && j < i; j++)
            front = front.next;
        if (i >= 0 && front.next != null) {
            T x = front.next.data;
            front.next = front.next.next;
            return x;
        }
        return null;
    }

    public void clear() {
        this.head.next = null;
    }

    public Node<T> search(T key) {
        for (Node<T> p = this.head; p != null; p = p.next)
            if (key.equals(p.data))
                return p;
        return null;
    }

    public T remove2(T key) {
        /* Node<T> behind=this.head;
        Node<T> front=behind.next;
        for (;front!=null;behind=front,front=front.next)
            if (key.equals(front.data)) {
                behind.next = front.next;
                return key;
            }
        return null;
         */
        for (Node<T> front = this.head, p = front.next; p != null; front = p, p = p.next) {
            if (key.equals(p.data))               //若查找成功
            {
                front.next = p.next;             //删除front的后继（p结点），包括头删除、中间/尾删除
                return p.data;
            }
        }
        return null;
    }

    public boolean isDifferent(SinglyList<T> list) {
        for (Node<T> first = this.head.next; first.next != null; first = first.next) {
            for (Node<T> second = first.next; second != null; second = second.next)
                if (first.data.equals(second.data))
                    return false;
        }
        return true;
    }

    /**
     * 基本思想 不从list.head 开始，从list.head.next出发，由于要用到三个指针，牵扯到链表的长度问题，
     * 需要单独将长度为2的链表单独讨论
     *
     * @param <T>
     * @param list
     */
    public static <T> void reverse(SinglyList<T> list) {
//        Node<T> front =list.head.next;
//        Node<T> p=front.next;
//        Node<T> behind=p.next;
//        while (front!=null){
//            p.next=front;
//            if (front==list.head.next)
//                front.next=null;
//            front=p;
//            p=behind;
//            behind=behind.next;
//            if (p==null)
//                list.head.next=front;
//        }
        Node<T> p = list.head.next, front = null;
        while (p != null) {
            Node<T> succ = p.next;
            p.next = front;
            front = p;
            p = succ;
        }
        list.head.next = front;
    }

    public void concat(SinglyList<T> list) {
        Node<T> p = this.head.next;
        while (p.next != null) {
            p = p.next;
        }
        p.next = list.head.next;
    }

    public void addAll(SinglyList<T> list) {
        SinglyList<T> list1 = new SinglyList<T>(list);
        concat(list1);
    }

    public SinglyList<T> union(SinglyList<T> list) {
        SinglyList<T> this1 = new SinglyList<T>(this);
        SinglyList<T> list1 = new SinglyList<T>(list);
        Node<T> p = this1.head.next;
        while (p.next != null) {
            p = p.next;
        }
        p.next = list1.head.next;
        return this1;
    }

    /**
     * void replaceAll(SinglyList<T> pattern, SinglyList<T> list)	//替换所有匹配子表为list（深拷贝）
     * 基本思路：所有意味着遍历至表尾，找到匹配子串则需要记录表头前一个结点的地址和表尾后一个结点的地址，为了方便记录，个人认为使用数组（顺序表）
     * 存储指针，便于存取，顺序为：表头前一结点地址，表中各结点地址，表尾后一结点地址
     * 防止出现多次匹配表，每找到一次匹配串，则需要将list表拷贝一次(旧)
     * 在3张表上加指针，patten表和this表上的一个指针进行数值比对，this表上另一个指针用于记录匹配串的前一个结点。
     **
     * @param pattern
     * @param list
     */
    public void replaceAll(SinglyList<T> pattern, SinglyList<T> list) {
        Node<T> front = this.head;
        Node<T> behind = this.head.next;
        Node<T> p = pattern.head.next;
      //  Node<T> p1 = list.head.next;

        if (this.size() < pattern.size())
            throw new UnsupportedOperationException("模式串长度超过文本长度！");

        while (behind != null) {
            if (behind.data == p.data) {    //第一个元素匹配成功
                while (behind != null && p != null && behind.data == p.data) {
                    behind = behind.next;
                    p = p.next;
                }
                if (p == null) {  //匹配完成
                    SinglyList<T> list1 = new SinglyList<T>(list);
                    front.next = list1.head.next;
                    Node<T> rear = list1.head;
                    while (rear.next != null) {
                        rear = rear.next;
                    }
                    rear.next = behind;
                    p = pattern.head.next;  //模式串指针恢复，下次匹配使用
                    /*
                    while (front3 != null) {  //深拷贝
                        front.next = new Node<T>(front3.data, null);
                        front = front.next;
                        front3 = front3.next;
                    }*/
                    //  front.next = front1;   //接入原this串的剩余子串
                    //   front3 = list.head.next;  //匹配完成后返回头结点，进行下一次深拷贝
                }
//                if (behind == null)
//                    return;
                p = pattern.head.next;  //匹配失败，模式串指针恢复，下次匹配使用
            }
            front = front.next;  //第一个元素匹配不成功，this表上的指针后移
            behind = front.next;
        }
    }

    public static void main(String[] args) {
        Integer[] a={1,2,3,4,5,6,7,23,34,11,12};
        Integer[] b={23,34};
        Integer[] c={8,9,10};

        SinglyList<Integer> a1=new SinglyList<Integer>(a);
        SinglyList<Integer> b1=new SinglyList<Integer>(b);
        SinglyList<Integer> c1=new SinglyList<Integer>(c);

        a1.replaceAll(b1,c1);
        System.out.println(a1.toString());
    }
}
